package cn.yuemouren.leetcode;

import java.util.*;

/**
 * @Author: Timi
 * @Description: 350. 两个数组的交集 II
 *      1.使用List实现
 *      2.使用Map实现
 * @Date: 2020/8/4 9:12
 */
public class Test_350 {
    /**
     * 未排序比较
     * @param nums1
     * @param nums2
     * @return
     */
    /*public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        List<Integer> resList = new ArrayList<>();
        for (int i : nums1) {
            list.add(i);
        }
        for (int i : nums2) {
            if (list.contains(i)) {
                resList.add(i);
                list.remove(Integer.valueOf(i));
            }
        }
        int index = 0;
        int[] res = new int[resList.size()];
        for (int i : resList)
            res[index++] = i;
        return res;
    }*/

    /**
     * 排序后按照顺序比较大小，相等入集合
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int index = 0,i = 0,j = 0;
        List<Integer> res = new ArrayList<>();
        while(i < nums1.length && j < nums2.length){
            if(nums1[i] > nums2[j]){
                j++;
            } else if(nums1[i] < nums2[j]){
                i++;
            } else {
                res.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] result = new int[res.size()];
        for (Integer num : res)
            result[index++] = num;
        return result;
    }
}
